package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

/**
 * @see <a href=https://leetcode.cn/problems/path-sum/>路径总和</a>
 */
public class HasPathSum112 {
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        return has(root, targetSum, 0);
    }

    private static boolean has(TreeNode root, int targetSum, int beforeSum) {
        if (root == null && beforeSum == targetSum) {
            return true;
        }
        if (root == null && beforeSum != targetSum) {
            return false;
        }
        if (root.left == null && root.right == null && root.val+beforeSum == targetSum) {
            return true;
        }
        if (root.left == null && root.right == null && root.val+beforeSum != targetSum) {
            return false;
        }
        beforeSum += root.val;
        boolean l = has(root.left, targetSum, beforeSum);
        boolean r = has(root.right, targetSum, beforeSum);
        return l||r;
    }

    public static void main(String[] args) {
        System.err.println(hasPathSum(TreeNode.generatorTreeNode(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1}), 22));
        System.err.println(hasPathSum(TreeNode.generatorTreeNode(new Integer[]{1,2}), 1));
    }
}
